package com.leetcode.partition8;

import java.util.Arrays;
import java.util.LinkedList;

/**
 * @author `RKC`
 * @date 2021/11/24 19:10
 */
public class LC785判断二分图 {

    public static void main(String[] args) {
//        int[][] graph = {{4, 1}, {0, 2}, {1, 3}, {2, 4}, {3, 0}};
        int[][] graph = {{1, 3}, {0, 2}, {1, 3}, {0, 2}};
        System.out.println(isBipartite(graph));
    }

    public static boolean isBipartite(int[][] graph) {
        int[] color = new int[graph.length];
        //0表示结点没有颜色，1表示结点为白色，2表示黑色，并尝试对每一个结点进行染色，如有冲突，则说明不是二分图
        for (int i = 0; i < graph.length; i++) {
            //如果当前结点已经被染色，就跳过
            if (color[i] != 0) continue;
//            if (!dfs(graph, i, color, 1)) return false;
            if (!bfs(graph, i, color)) return false;
        }
        return true;
    }

    private static boolean bfs(int[][] graph, int i, int[] color) {
        LinkedList<int[]> queue = new LinkedList<>();
        color[i] = 1;
        queue.addLast(new int[]{i, 1});
        while (!queue.isEmpty()) {
            int[] cur = queue.pollFirst();
            int u = cur[0], c = cur[1];
            //给周围结点染上相反的颜色
            for (int j = 0; j < graph[u].length; j++) {
                int v = graph[u][j];
                if (color[v] == c) return false;
                if (color[v] == 0) {
                    color[v] = 3 - c;
                    queue.addLast(new int[]{v, 3 - c});
                }
            }
        }
        return true;
    }

    private static boolean dfs(int[][] graph, int u, int[] color, int curColor) {
        //将当前结点染色
        color[u] = curColor;
        for (int i = 0; i < graph[u].length; i++) {
            int v = graph[u][i];
            //如果周边结点已经被染色，则检查颜色是否和当前结点的颜色相反，相反则直接返回；如果周边结点没有被染色，则进行染相反的颜色
            if (color[v] == curColor) return false;
            if (color[v] == 0 && !dfs(graph, v, color, 3 - curColor)) return false;
        }
        return true;
    }
}
